#define _CRT_SECURE_NO_WARNINGS	

#define MAX 100001
typedef struct TreeNode TreeNode;
bool isEvenOddTree(struct TreeNode* root)
{
    TreeNode* arr[MAX];
    int front = 0;
    int rear = 0;
    int flag = 0;
    int pre;
    arr[rear++] = root;
    while (front != rear)
    {
        int gap = rear - front;
        if (flag == 0)
            pre = 0;
        if (flag == 1)
            pre = 1000001;
        for (int i = 0; i < gap; i++)
        {
            TreeNode* newroot = arr[front++];
            if (flag == 0)
                if (newroot->val % 2 != 1 || pre >= newroot->val)
                    return false;
            if (flag == 1)
                if (newroot->val % 2 != 0 || pre <= newroot->val)
                    return false;
            pre = newroot->val;
            if (newroot->left)
                arr[rear++] = newroot->left;
            if (newroot->right)
                arr[rear++] = newroot->right;
        }
        flag = (flag + 1) % 2;
    }
    return true;
}